package com.shi.algorithm.binary_search;

import java.util.Arrays;

public class BinarySearch {

    /**
     * 二分查找基础版
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchBasics(int[] arr, int target) {
        //arr = 1，2，3，4，5，6，7，8，9
        int i = 0;
        int j = arr.length - 1;

        while (i <= j) {
            int m = (i + j) >>> 1;    //等价于 int m = (i + j) / 2;
            //思考：为什么用 >>>1 ?

            if(target < arr[m]){
                j = m - 1;
            } else if (target > arr[m]) {
                i = m + 1;
            } else {
                //target = arr[m]
                //找到了，返回下标m
                return m;
            }
        }
        //没找到
        return -1;
    }
    /*
        问题1: 为什么是 i<=j 意味着区间内有未比较的元素, 而不是 i<j ?
           i==j 意味着 i,j 它们指向的元素也会参与比较
           i<j 只意味着 m 指向的元素参与比较
        问题2: (i + j) / 2 有没有问题?
        问题3: 都写成小于号有啥好处?
     */

    /**
     * 二分查找改动版
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchAlternative(int[] arr, int target){
        //arr = 1，2，3，4，5，6，7，8，9
        int i = 0;
        int j = arr.length;

        while (i < j) {
            int m = (i + j) >>> 1;    //等价于 int m = (i + j) / 2;
            //思考：为什么用 >>>1 ?

            if(target < arr[m]){
                j = m;
            } else if (arr[m] < target) {
                i = m + 1;
            } else {
                //target = arr[m]
                //找到了，返回下标m
                return m;
            }
        }
        //没找到
        return -1;
    }


    /**
     * 二分查找平衡版：解决：基础版目标值在最左边，查找L次；在最右边，查找2*L次，左右不平衡
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchBalance(int[] arr, int target){
        int i = 0;
        int j = arr.length;
        while (1 < j - i){//要查找的范围 > 1 时
            int m = (i + j) >>> 1;

            if(target < arr[m]){
                j = m;
            } else {
                i = m;
            }
        }

        return (target == arr[i]) ? i : -1;
    }

    /**
     * 二分查找Java版
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchJava(int[] arr, int target){

        //分析源码
        return Arrays.binarySearch(arr, target);
    }

    /**
     * 二分查找 Leftmost基础版
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchLeftmost1(int[] arr, int target){
        //arr[] = 1,2,3,4,4,4,4,5,5,5,6,7,8

        int i = 0;
        int j = arr.length - 1;

        int candidate = -1;

        while (i <= j){
            int m = (i + j) >>> 1;
            if(target < arr[m]){
                j = m - 1;
            } else if (arr[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                j = m - 1;
            }
        }

        return candidate;
    }

    /**
     * 二分查找 Rightmost基础版
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchRightmost1(int[] arr, int target){
        //arr[] = 1,2,3,4,4,4,4,5,5,5,6,7,8

        int i = 0;
        int j = arr.length - 1;

        int candidate = -1;

        while (i <= j){
            int m = (i + j) >>> 1;
            if(target < arr[m]){
                j = m - 1;
            } else if (arr[m] < target) {
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }

        return candidate;
    }

    /**
     * 二分查找 Leftmost改良版
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchLeftmost2(int[] arr, int target){
        //arr[] = 1,2,3,4,4,4,4,5,5,5,6,7,8

        int i = 0;
        int j = arr.length - 1;

        while (i <= j){
            int m = (i + j) >>> 1;
            if(target <= arr[m]){
                j = m - 1;
            } else {
                i = m + 1;
            }
        }

        return i;
    }

    /**
     * 二分查找 Rightmost改良版
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearchRightmost2(int[] arr, int target){
        //arr[] = 1,2,3,4,4,4,4,5,5,5,6,7,8

        int i = 0;
        int j = arr.length - 1;

        while (i <= j){
            int m = (i + j) >>> 1;
            if(target < arr[m]){
                j = m - 1;
            } else {
                i = m + 1;
            }
        }

        return i - 1;
    }
}
















